【LeetCode 394】 Decode String 字符串解码

发表于 | 分类于

[LeetCode 394]Decode String 字符串解码

Problem decription:

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example:

1
2
3
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

Solution：

首先想到的是递归，或者是用两个栈的非递归方法，非递归的效率更高一些。
一个栈用来保存数字，一个用来保存字符串，以 b3[a]2[c]d] 为例,遍历整个字符串，用t保存当前字符串，count保存当前数字，碰到字母就添加到t中，碰到数字便循环读取并转换成正确的格式，当读取到‘[’时，将count入数字栈，将当前字符入字符栈，并将t清空，当读取到‘]’时，去数字栈顶元素k与字符栈顶元素s，t=s+k个t，直至栈为空结束，t即为所求。

1

2

Code：

//beat 50%
class Solution {

    public String decodeString(String s) {
        Stack<Integer> sNum=new Stack<Integer>();
        Stack<String> sStr=new Stack<String>();
        char[] chr=s.toCharArray();
        String t="";
        String count="";

        for(int i=0;i<chr.length;i++){
            if(chr[i]>='0' && chr[i]<='9'){
                while(chr[i]!='['){
                    count+=chr[i++];
                }
                sNum.push(Integer.parseInt(count));
                count="";

            }
           else if(chr[i]<'0' || chr[i]>'9' &&chr[i]!=']' &&chr[i]!='[')
                t+=chr[i];

           if(chr[i]=='['){
            sStr.push(t);
            t="";
        }
            if(chr[i]==']'){
                int k=1;
                if(!sNum.isEmpty()){
                    k=sNum.pop();

                String top=sStr.pop();
                for(int j=0;j<k;j++)
                    top+=t;  
                t=top;    
                }
            }


        }
        return t;
    }
}
Thanks!